It is known within the field of data processing systems to provide data stores with entries which are replaced under control of a replacement mechanism during ongoing operation. Such data stores are commonly, although not exclusively, used to predict data with the aim of increasing processing speed and exploiting higher degrees of instruction level parallelism. As an example, value predictors and branch predictors are known which keep a history of previous instructions in order to predict the data or outcome of an upcoming instruction. Such mechanisms can be highly successful in increasing performance.
A significant disadvantage associated with such known prediction mechanisms is that they have large overhead in terms of the circuit area and power which they consume. Typically, in order to be effective at providing a high degree of prediction, such mechanisms need to store a large numbers of entries. However, in practice only a subset of these entries are useful and a large number of the entries contain non-useful data. Examples of such non-useful data are non-regular (unpredictable) entries in a value predictor or branches that have non-regular behaviour or happen very rarely in a branch predictor. However, if one attempts to reduce the number of entries within such structures in order to reduce their associated overhead, there is a significant degradation in the prediction accuracy. As an example, using smaller structures with fewer entries will normally have the effect that useful entries will be evicted by different non-useful entries rendering the predictor less effective.
Known prior techniques seeking to address the above problems mainly focus on replacement policies that decide which entry in a predictor table will be replaced based upon its performance using event counters [2, 3] or hysteresis counters. Event counters keep track of the performance of each entry based upon different events such as miss or hit. Hysteresis counters provide for a delay in the replacement of an entry so as to avoid premature replacement. There are also various known techniques [4, 5] to filter the instructions that update the predictors. Such filtering reduces the pressure on entry capacity due to excessive replacements and improves the prediction accuracy. In addition, confidence history may be used in order to avoid replacing entries that deliver good predictions by others that have poor prediction accuracy. Nevertheless, these methods rely on having large storage capacities within the data stores to achieve accurate predictions. With smaller data stores it is impractical to use, for example, hysteresis counters since there is not enough time when the entries are present in the data store to get hits which increase the counter numbers to meaningful levels.